package com.dycong.common.leetcode;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * @author dycong
 * @date 2019/12/10 9:28
 */
public class TriangleGenerate_II_119 {

    public static void main(String[] args) {
        TriangleGenerate_II_119 triangleGenerate_118 = new TriangleGenerate_II_119();
        System.out.println(triangleGenerate_118.getRow2(21));
        System.out.println(triangleGenerate_118.getRow(21));
        System.out.println(triangleGenerate_118.getRow0(21));
    }

    /**
     * 杨辉三角
     * 既然已经做到了这道题，你肯定对杨辉三角已经有一个基本的了解了。
     * 从数学的角度上来说，杨辉三角的每一项都对应着(a + b)的n次方展开后每一项的系数。
     * 由于这道题需要得出的是第N行的内容，那么第一反应想到通过通项公式来计算得出每一项填充到数组里就是很自然的事情了。
     * <p>
     * 1、式算
     * todo 从 1 开始，第n行第k列的值，可以通过通项公式：(n-1)!/(k-1)!(n-k)! 计算得到
     * todo 从 0 开始，第n行第k列的值，可以通过通项公式：n!/k!(n-k)! 计算得到
     * todo 由 n!/k!(n-k)!  并假设（k=k-1），可得：Ck = ((n-k+1)/k) * Ck-1
     *
     * @param rowIndex
     * @return
     */

    public List<Integer> getRow0(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        //todo int 会越界
        long pre = 1;
        res.add((int) pre);
        if (rowIndex < 1) {
            return res;
        }
        int medium = rowIndex / 2;
        for (int i = 1; i <= rowIndex; i++) {
            if (i > medium) {
                for (; i <= rowIndex; i++) {
                    res.add(res.get(rowIndex - i));
                }
                break;
            }

            //todo 先乘法后除法，增加准确度，否则会由于精度丢失造成结果错误
            long cur = pre * (rowIndex - i + 1) / i;
            pre = cur;
            res.add((int) cur);
        }
        return res;
    }

    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        long pre = 1;
        res.add((int) pre);
        if (rowIndex < 1) {
            return res;
        }
        for (int i = 1; i <= rowIndex; i++) {
            //todo 先乘法后除法，增加准确度
            long cur = pre * (rowIndex - i + 1) / i;
            pre = cur;
            res.add((int) cur);
        }
        return res;
    }

    public List<Integer> getRow2(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        if (rowIndex <= 0) {
            return res;
        }
        for (int i = 0; i <= rowIndex; i++) {
            int cur = factorial(rowIndex).divide((factorial(i).multiply(factorial(rowIndex - i))), BigDecimal.ROUND_UNNECESSARY).intValue();
            res.add(cur);
        }
        return res;
    }


    public List<Integer> getRow_(int rowIndex) {
        rowIndex++;
        List<Integer> res = new ArrayList<>();
        if (rowIndex <= 0) {
            return res;
        }
        res.add(1);
        for (int i = 2; i < rowIndex; i++) {
            int cur = factorial(rowIndex).divide((factorial(i).multiply(factorial(rowIndex - i))), BigDecimal.ROUND_UNNECESSARY).intValue();
            res.add(cur);
        }
        res.add(1);
        return res;
    }

    /**
     * 使用long计算阶乘，int会越界
     *
     * @param num
     * @return
     */
    private long factorial_long(int num) {
        if (num < 2) {
            return 1L;
        }
        return num * factorial_long(num - 1);
    }

    private BigDecimal factorial(int num) {
        if (num < 2) {
            return BigDecimal.ONE;
        }
        return BigDecimal.valueOf(num).multiply(factorial(num - 1));
    }
    /**
     * 3、通用优化逻辑
     * 还有没有办法提升时间？
     * 当然有
     *
     * todo 不管是式算还是图算，整个过程中伴随着大量的计算，仔细观察，我们可以发现杨辉三角是左右对称的。
     * todo 所以可以在过半以后，把关于中轴对称的内容直接复制过来
     */
}
